#include <iostream>
#include <algorithm>
#include <numeric>
#include <utility>
#include <functional>
#include <vector>
#include <map>
#include <string>
class Node {
public:
Node(int num) : num(num) {}
void push(Node* linked);
bool isLinked(int num);
std::vector<int> linkedNum(void);
private:
int num;
std::vector<Node*> linked;
};
void Node::push(Node *linked) { this->linked.push_back(linked); }
bool Node::isLinked(int num) {
for(auto iter=this->linked.begin(); iter!=this->linked.end(); ++iter) if((*iter)->num==num) return true;
return false;
}
std::vector<int> Node::linkedNum(void) {
std::vector<int> result;
for(auto iter=this->linked.begin(); iter!=this->linked.end(); ++iter) result.push_back((*iter)->num);
return result;
}
class Road {
public:
Road(int num);
void updateRoads(std::vector<std::pair<int, int>>);
int minTeleport(void);
private:
void findRoute(std::vector<int>, int, int&);
std::vector<int> teleportAble(std::vector<int> path);
int num;
std::vector<Node> nodes;
};
Road::Road(int num): num(num) {
for(int i=1; i<=num; ++i) this->nodes.push_back(Node(i));
}
void Road::updateRoads(std::vector<std::pair<int, int>> roads) {
for(auto road : roads) {
this->nodes[road.first-1].push(&this->nodes[road.second-1]);
}
}
auto includeAll = [](const std::vector<int> vec, int num) {
std::vector<bool> checker(num, false);
for (auto iter = vec.begin(); iter != vec.end(); ++iter)
checker[*iter - 1] = true;
return std::accumulate(checker.begin(), checker.end(), 0) == num;
};
auto makeNewVecWithAppend = [](const std::vector<int> vec, int value) {
std::vector<int> newVec = vec;
newVec.push_back(value);
return newVec;
};
auto amIbeen = [](const std::vector<int> path, int from) {
std::vector<int> ban;
for (int i = 0; i < path.size() - 1; ++i) {
if (path[i] == from)
ban.push_back(path[i + 1]);
}
return ban;
};
auto isMember = [](const std::vector<int> vec, int value) {
for (auto iter = vec.begin(); iter != vec.end(); ++iter)
if (*iter == value)
return true;
return false;
};
std::vector<int> Road::teleportAble(std::vector<int> path) {
std::vector<int> teleportAble;
std::map<int, int> linkmap;
for(int i=1; i<=this->num; ++i) linkmap[i]=0;
for(int i=0; i<this->nodes.size(); ++i) {
std::vector<int> linked=this->nodes[i].linkedNum();
linkmap[i+1]=linked.size();
}
for(int i=0; i<path.size()-1; ++i) {
linkmap[path[i]]--;
}
for(auto iter=linkmap.begin(); iter!=linkmap.end(); ++iter) {
if(iter->second>0) teleportAble.push_back(iter->first);
}
return teleportAble;
}
void Road::findRoute(std::vector<int> path, int telCount, int& minTel) {
if(includeAll(path, this->num)) {
if(telCount<minTel) minTel=telCount;
return;
}
int now=path.back(), possibleWay=0;
std::vector<int> next=this->nodes[now-1].linkedNum();
std::vector<int> banned=amIbeen(path, now);
for(auto iter=next.begin(); iter!=next.end(); ++iter) {
if(!isMember(banned, *iter)) {
this->findRoute(makeNewVecWithAppend(path, *iter), telCount, minTel);
possibleWay++;
}
}
if(possibleWay==0) {
std::vector<int> teleport=this->teleportAble(path);
for(auto iter=path.begin(); iter!=path.end(); ++iter) {
if(isMember(teleport, *iter)) {
this->findRoute(makeNewVecWithAppend(path, *iter), telCount+1, minTel);
}
}
}
return;
}
int Road::minTeleport(void) {
std::vector<int> been={1};
int minTel=std::numeric_limits<int>::max();
this->findRoute(been, 0, minTel);
return minTel;
}
int main(void) {
int n1=6;
std::vector<std::pair<int, int>> roads1={
{1, 2}, {2, 6}, {2, 4}, {4, 3}, {3, 2}, {3, 5}
};
int n2=5;
std::vector<std::pair<int, int>> roads2={
{1, 2}, {2, 3}, {3, 4}, {4, 5}
};
int n3=8;
std::vector<std::pair<int, int>> roads3={
{6, 4}, {2, 3}, {1, 6}, {4, 5},
{1, 2}, {1, 8}, {3, 7}, {7, 2}
};
int n4=9;
std::vector<std::pair<int, int>> roads4={
{1, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 5},
{5, 6}, {5, 7}, {6, 9}, {7, 9}, {5, 8}
};
int n5=7;
std::vector<std::pair<int, int>> roads5={
{1, 2}, {2, 3}, {3, 4}, {4, 5},
{3, 6}, {1, 7}, {7, 4}
};
Road road(n5);
road.updateRoads(roads5);
int result=road.minTeleport();
std::cout<<"Result: "<<result<<std::endl;
return 0;
}